%{
#include <stdio.h>
#include "attr.h"
#include "instrutil.h"
int yylex();
void yyerror(char * s);
#include "symtab.h"
#include "list.h"
#include "hashtab.h"

#define HASH_TABLE_SIZE 347

FILE *outfile;
char *CommentBuffer;
extern int optimize_flag; 

int offset = 0;
struct node *id_list; 
int word_size = 4;
enum hs {LHS, RHS};

int arithmetic(int, int, int);
int compare(int, int, int);
void setOffsets(struct node *, int, int);
int get_array_addr(char *, int, int, int);
int get_1d_offset(int, int, int, char *);
int get_2d_offset(int, int, int, int, char *);
void array_load_comment(int, char *, int);
void ctrlexp_helper(char *, int, int);
void for_helper(char *, int[], int);
void emit_optimized(int, Opcode_Name, int, int, int);
%}

%union {tokentype token;
        infonode myinfo;
       }

%token PROG PERIOD VAR 
%token INT WRITELN THEN IF 
%token DO ARRAY OF REPEAT
%token BEG END ASG  
%token EQ NEQ LT LEQ 
%token ELSE
%token FOR UNTIL
%token <token> ID ICONST 

%start program

%nonassoc EQ NEQ LT LEQ 
%left '+' '-' 
%left '*' 

%nonassoc THEN
%nonassoc ELSE

%type <myinfo> block variables vardcls vardcl type idlist stmtlist stmt cmpdstmt writestmt ifstmt ifhead fstmt rstmt ctrlexp
%type <myinfo> astmt lhs exp condexp

%%
program : {emitComment("Assign STATIC_AREA_ADDRESS to register \"r0\"");
           emit_optimized(NOLABEL, LOADI, STATIC_AREA_ADDRESS, 0, EMPTY);} 
           PROG ID ';' block PERIOD { }
	;

block	: variables cmpdstmt { }
	;

variables: /* empty */
	| VAR vardcls { }
	;

vardcls	: vardcls vardcl ';' { }
        | vardcl ';' { }
	| error ';' { yyerror("***Error: illegal variable declaration\n");}  
	;

vardcl	: {id_list = emptyList();}
          idlist ':' type {
	                    setOffsets(id_list, $4.vals[0], $4.vals[1]);
	                  }
	;

type	: INT 	{
                  $$.vals[0] = 0;
                  $$.vals[1] = 0;
	        }
        | ARRAY '[' ICONST ']' OF INT	{
	                                  $$.vals[0] = $3.num;
					  $$.vals[1] = 0;
	                                }
        | ARRAY '[' ICONST ',' ICONST ']' OF INT {
	                                           $$.vals[0] = $3.num;
						   $$.vals[1] = $5.num;
	                                         }
	;

idlist	: idlist ',' ID { 
                          insert($3.str);
			  id_list = add($3.str, id_list);
	                }
        | ID		{
	                  insert($1.str);
			  id_list = add($1.str, id_list);
	                }
	;

stmtlist : stmtlist ';' stmt { }
	| stmt { }
        | error { yyerror("***Error: ';' expected or illegal statement \n");}
	;

stmt    : ifstmt { }
	| fstmt { }
        | rstmt { }
	| astmt { }
	| writestmt { }
	| cmpdstmt { }
	;

cmpdstmt: BEG stmtlist END { }
	;

ifstmt :  ifhead {
                   /* branch depending on the condition */
                   int label1 = NextLabel();
		   int label2 = NextLabel();
		   emit_optimized(NOLABEL, CBR, $1.val, label1, label2);

		   emit_optimized(label1, NOP, EMPTY, EMPTY, EMPTY);
		   emitComment("This is the \"true\" branch");
		   $<myinfo>$.val = label2;
	         }
          THEN stmt {
	              emit_optimized($<myinfo>2.val, NOP, EMPTY, EMPTY, EMPTY);
	              emitComment("This is the \"false\" branch");
	            } 
        |  ifhead {
                    /* branch depending on the condition */
                    int then_label = NextLabel();
		    int else_label = NextLabel();
		    emit_optimized(NOLABEL, CBR, $1.val, then_label, else_label);

		    emit_optimized(then_label, NOP, EMPTY, EMPTY, EMPTY);
		    emitComment("This is the \"true\" branch");
		    $<myinfo>$.val = else_label;
	          }
           THEN stmt {
	               int after_if_label = NextLabel();
		       emit_optimized(NOLABEL, BR, after_if_label, EMPTY, EMPTY);
		       emit_optimized($<myinfo>2.val, NOP, EMPTY, EMPTY, EMPTY);
		       emitComment("This is the \"false\" branch");
		       $<myinfo>$.val = after_if_label;
	             }
           ELSE stmt { 
	               emit_optimized($<myinfo>5.val, NOP, EMPTY, EMPTY, EMPTY);
	               emitComment("This is the \"false\" branch");
	             }
 	;

ifhead : IF condexp {
                      /* the boolean result is returned in a register */
                      $$.val = $2.val;
	            }
        ;

writestmt: WRITELN '(' exp ')' {
                                 emitComment("Code for \"WRITE\"");
				 emit_optimized(NOLABEL, STOREAI, $3.val, 0, offset);
				 emit_optimized(NOLABEL, OUTPUT, STATIC_AREA_ADDRESS + offset, EMPTY, EMPTY);
				 offset += 4;
	                       }
	;

fstmt	: FOR ctrlexp {
                        for_helper($2.str, $<myinfo>$.vals, 2);
	              }
          DO stmt {
	            /* increment loop counter variable */
                    SymTabEntry *e = lookup($2.str);
		    int ofst = e->offset;

	            int reg1 = NextRegister();
		    int reg2 = NextRegister();
		    emit_optimized(NOLABEL, LOADAI, 0, ofst, reg1);
		    emit_optimized(NOLABEL, ADDI, reg1, 1, reg2);
		    emit_optimized(NOLABEL, STOREAI, reg2, 0, ofst);
		    emit_optimized(NOLABEL, BR, $<myinfo>3.vals[0], EMPTY, EMPTY);
		    emit_optimized($<myinfo>3.vals[1], NOP, EMPTY, EMPTY, EMPTY);
	          } 
	;

rstmt   : REPEAT {
                   int begin_label = NextLabel();
                   emit_optimized(begin_label, NOP, EMPTY, EMPTY, EMPTY);
		   emitComment("Body of \"REPEAT\" construct starts here");
		   $<myinfo>$.val = begin_label;
	         }
          stmt UNTIL condexp {
	                       int end_label = NextLabel();
			       int return_label = NextLabel();
			       emit_optimized(NOLABEL, CBR, $5.val, end_label, return_label);
			       emitComment("Control code for \"REPEAT UNTIL\"");
			       emit_optimized(return_label, BR, $<myinfo>2.val, EMPTY, EMPTY);
			       emit_optimized(end_label, NOP, EMPTY, EMPTY, EMPTY);
	                     }
        ;

astmt : lhs ASG exp {
                      emit_optimized(NOLABEL, STORE, $3.val, $1.val, EMPTY);
		    }
	;

lhs	:  ID			    { 
                                      /* Calculate virtual address of ID into a register */
                                      SymTabEntry *e = lookup($1.str);
				      int ofst = e->offset;
				      int reg1 = NextRegister();
				      int reg2 = NextRegister();
				      char *comment = malloc(75);

				      sprintf(comment, "%s%s%s%d", "Load LHS value of variable \"", $1.str, "\" at offset ", ofst);
				      emitComment(comment);
				      free(comment);
				      emit_optimized(NOLABEL, LOADI, ofst, reg1, EMPTY);
				      emit_optimized(NOLABEL, ADD, 0, reg1, reg2);
	                              $$.val = reg2;
	                            }
        |  ID '[' exp ']'	    {
	                              $$.val = get_array_addr($1.str, $3.val, 0, LHS);
	                            }
        |  ID '[' exp ',' exp ']'   {
	                              $$.val = get_array_addr($1.str, $3.val, $5.val, LHS);
	                            }
        ;

exp	: exp '+' exp		{ 
                                  $$.val = arithmetic($1.val, ADD, $3.val);
	                        } 
        | exp '-' exp		{
                                  $$.val = arithmetic($1.val, SUB, $3.val);
	                        }
	| exp '*' exp		{
                                  $$.val = arithmetic($1.val, MULT, $3.val);
	                        }
        | ID			{ 
                                  /* Calculate virtual address of a variable and load it's value from the memory into a register */
	                          SymTabEntry *e = lookup($1.str);
				  int ofst = e->offset;
				  int reg1 = NextRegister();
				  char *comment = malloc(75);

				  sprintf(comment, "%s%s%s%d", "Load RHS value of variable \"", $1.str, "\" at offset ", ofst);
				  emitComment(comment);
				  free(comment);
				  emit_optimized(NOLABEL, LOADAI, 0, ofst, reg1);
				  $$.val = reg1;
	                        } 
        | ID '[' exp ']'	{
	                          $$.val = get_array_addr($1.str, $3.val, 0, RHS);
	                        }
        | ID '[' exp ',' exp ']' {
	                           $$.val = get_array_addr($1.str, $3.val, $5.val, RHS);
	                         }
	| ICONST                 { int reg = NextRegister();
  	                           emit_optimized(NOLABEL, LOADI, $1.num, reg, EMPTY);
		         	   $$.val = reg;}
	| error { yyerror("***Error: illegal expression\n");}  
	;


ctrlexp	: ID ASG ICONST ',' ICONST {
                                     ctrlexp_helper($1.str, $3.num, $5.num);

				     /* Return the ID string */
				     $$.str = malloc(strlen($1.str)); // NEED TO FREE THIS AT SOME POINT!
				     strcpy($$.str, $1.str);
	                           }
        ;


condexp	: exp NEQ exp		{
                                  $$.val = compare($1.val, CMPNE, $3.val);
	                        }
	| exp EQ exp		{
                                  $$.val = compare($1.val, CMPEQ, $3.val);
	                        }
	| exp LT exp		{
                                  $$.val = compare($1.val, CMPLT, $3.val);
	                        }
	| exp LEQ exp		{
                                  $$.val = compare($1.val, CMPLE, $3.val);
	                        }
	| error { yyerror("***Error: illegal conditional expression\n");}  
        ;

%%

void yyerror(char* s) {
        fprintf(stderr,"%s\n",s);
        }

/*
  arithmetic()
       performs operation and returns the register in which the value resides.
*/
int arithmetic(int reg1, int operation, int reg2) {
  int reg = NextRegister();
  emit_optimized(NOLABEL, operation, reg1, reg2, reg);
  return reg;
}

/*
  compare()
      compares the values in the two registers using the comparison operator
      and returns the register containing the boolean result.
 */
int compare(int reg1, int comp_op, int reg2) {
  int reg = NextRegister();
  emit_optimized(NOLABEL, comp_op, reg1, reg2, reg);
  return reg;
}

/*
  setOffsets()
      sets the offsets in the symbol table for each node in the list.
*/
void setOffsets(struct node *list, int dim1, int dim2) {
  if(list == NULL) {
    return;
  }

  setOffsets(rest(list), dim1, dim2);

  char *id = first(list);
  SymTabEntry *e = lookup(id);

  e->offset = offset;
  if(dim1 == 0) {
    offset += 4;
  } else if(dim2 == 0) {
    offset = offset + (4 * dim1);
  } else {
    offset = offset + (4 * dim1 * dim2);
  }

  e->dim1 = dim1;
  e->dim2 = dim2;

  free(list); // MAKE SURE THIS DOESN'T CAUSE PROBLEMS!
}

/*
  get_array_addr()
      gets the virtual address or value of id[dim1]{[dim2]}.
 */
int get_array_addr(char *id, int dim1, int dim2, int hs) {
  SymTabEntry *e = lookup(id);
  int ofst = e->offset;
  int reg1 = NextRegister();
  int reg2;

  if(dim2 == 0) {
    reg2 = get_1d_offset(dim1, ofst, hs, id);
  } else {
    reg2 = get_2d_offset(dim1, dim2, ofst, hs, id);
  }

  if(hs == LHS) {
    emit_optimized(NOLABEL, ADD, 0, reg2, reg1);
  } else if(hs == RHS) {
      emit_optimized(NOLABEL, LOADAO, 0, reg2, reg1);
    }

  return reg1;
}

int get_1d_offset(int dim1, int array_base, int hs, char *id) {
  int reg1 = NextRegister();
  int reg2 = NextRegister();
  int reg3 = NextRegister();
  int reg4 = NextRegister();

  array_load_comment(hs, id, array_base);
  emit_optimized(NOLABEL, LOADI, word_size, reg1, EMPTY);
  emit_optimized(NOLABEL, MULT, dim1, reg1, reg2);
  emit_optimized(NOLABEL, LOADI, array_base, reg3, EMPTY);
  emit_optimized(NOLABEL, ADD, reg3, reg2, reg4);

  return reg4;
}

int get_2d_offset(int reg1, int reg2, int array_base, int hs, char *id) {
  int reg4 = NextRegister();
  int reg5 = NextRegister();
  int reg6 = NextRegister();
  int reg7 = NextRegister();
  int reg8 = NextRegister();
  int reg9 = NextRegister();
  int reg10 = NextRegister();

  SymTabEntry *e = lookup(id);

  array_load_comment(hs, id, array_base);
  emit_optimized(NOLABEL, LOADI, word_size, reg4, EMPTY);
  emit_optimized(NOLABEL, LOADI, e->dim1, reg5, EMPTY);
  emit_optimized(NOLABEL, MULT, reg5, reg2, reg6);
  emit_optimized(NOLABEL, ADD, reg6, reg1, reg7);
  emit_optimized(NOLABEL, MULT, reg7, reg4, reg8);
  emit_optimized(NOLABEL, LOADI, array_base, reg9, EMPTY);
  emit_optimized(NOLABEL, ADD, reg9, reg8, reg10);

  return reg10;
}

void array_load_comment(int hs, char *id, int ofst) {
  char *comment = malloc(75);

  char *str;
  if(hs == LHS) {
    str = "LHS";
  } else if(hs == RHS) {
      str = "RHS";
    }

  sprintf(comment, "%s%s%s%s%s%d", "Load ", str, " value of array variable \"", id, "\" with based address ", ofst);
  emitComment(comment);
  free(comment);
}

/* 
  ctrlexp_helper()
      sets the loop counter limits in the symbol table entry.
*/
void ctrlexp_helper(char *id, int lower, int upper) {
  SymTabEntry *e = lookup(id);
  e->dim1 = lower;
  e->dim2 = upper;
}

// size is currently not being used.
void for_helper(char *id, int labels[], int size) {
  SymTabEntry *e = lookup(id);
  int ofst = e->offset;

  char *comment = malloc(75);
  sprintf(comment, "%s%s%s%d%s%d", "Initialize ind. variable \"", id, "\" at offset ", ofst, " with lower bound value ", e->dim1);
  emitComment(comment);
  free(comment);

  /* load loop counter limits into registers*/
  int reg1 = NextRegister();
  int reg2 = NextRegister();
  int reg3 = NextRegister();
  int reg4 = NextRegister();
  int reg5 = NextRegister();
  int reg6 = NextRegister();
  emit_optimized(NOLABEL, LOADI, ofst, reg1, EMPTY);
  emit_optimized(NOLABEL, ADD, 0, reg1, reg2);
  emit_optimized(NOLABEL, LOADI, e->dim1, reg5, EMPTY);
  emit_optimized(NOLABEL, LOADI, e->dim2, reg6, EMPTY);
  emit_optimized(NOLABEL, STORE, reg5, reg2, EMPTY);

  int header_label = NextLabel();
  int begin_label = NextLabel();
  int end_label = NextLabel();
  emitComment("Generate control code for \"FOR\" ");
  emit_optimized(header_label, LOADAI, 0, ofst, reg3); /* loop counter variable */

  /* testing condition */
  emit_optimized(NOLABEL, CMPLE, reg3, reg6, reg4);
  emit_optimized(NOLABEL, CBR, reg4, begin_label, end_label);

  emit_optimized(begin_label, NOP, EMPTY, EMPTY, EMPTY);

  labels[0] = header_label;
  labels[1] = end_label;
}

/*
  emit_optimized()
      If the optimize_flag is set to 1, then the instruction is passed through
      the optimizer. Else, emit_optimized() is called.
 */
void emit_optimized(int label_index, Opcode_Name opcode, int field1,
		    int field2, int field3) {
  if(optimize_flag == 1) {

    //    int result = build_dag(opcode, field1, field2, field3);
    int result = -1;
    
    /* optimization doesn't have an effect on this instruction */
    if(result == -1) {

      emit(label_index, opcode, field1, field2, field3, result);

    } else {

      emitCommentSym();
      emit(label_index, opcode, field1, field2, field3, result);

    }

  } else {
    emit(label_index, opcode, field1, field2, field3, -1);
  }
}

int build_dag(Opcode_Name opcode, int field1, int field2, int field3) {

  /*  char *f2 = malloc(5);
      sprintf(f2, "%c%d", 'r', field2);*/

  /* creating a leaf */
  /*  if(hashLookup(f2) == NULL) {
    HashTabEntry *e = hashInsert(f2);
    e->id = field2;
    e->list = NULL;
    e->child1 = NULL;
    e->child2 = NULL;
    e->parent = NULL;
  } 

  if(hashLookup(f1) == NULL) {
    
  }*/

  return -1;
}


int optimize_flag = 0;


int
main(int argc, char* argv[]) {

  printf("\n     CS515 Fall 2011 Compiler\n");

  if (argc == 2 && strcmp(argv[1],"-O") == 0) {
    optimize_flag = 1;
    printf("    Version 1.0 CSE OPTIMIZER \n\n");

    // setup optimizer data-structure
    InitHashTable();
  }
    else
    printf("    Version 1.0 (non-optimizing)\n\n");
  
  outfile = fopen("iloc.out", "w");
  if (outfile == NULL) { 
    printf("ERROR: cannot open output file \"iloc.out\".\n");
    return -1;
  }

  CommentBuffer = (char *) malloc(500);  
  InitSymbolTable();

  printf("1\t");
  yyparse();
  printf("\n");

  PrintSymbolTable();

  fclose(outfile);
  
  return 1;
}
